#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int maxProduct(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n), g(n);
        int ret = nums[0];

        f[0] = g[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = max(max(nums[i], f[i - 1] * nums[i]), g[i - 1] * nums[i]);
            g[i] = min(min(nums[i], g[i - 1] * nums[i]), f[i - 1] * nums[i]);

            ret = max(ret, f[i]);
        }
        return ret;
    }

};
class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        vector<int> f;

        for (auto e : nums)
        {
            if (f.size() == 0 || e > f.back())
            {
                f.push_back(e);
            }
            else
            {
                int left = 0, right = f.size() - 1;
                while (left < right)
                {
                    int mid = left + (right - left) / 2;
                    if (f[mid] >= e) right = mid;
                    else left = mid + 1;
                }
                f[left] = e;
            }
        }
        return f.size();
    }
};
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;

        s = " " + s;

        unordered_set<string> hash;
        for (auto& e : wordDict) hash.insert(e);

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= i; j++)
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                };
            }
        }

        return dp[n];
    }
};
class Solution {
public:
    int coinChange(vector<int>& coins, int n)
    {
        const int INF = 0x3f3f3f3f;
        int m = coins.size();
        vector<int> dp(n + 1, INF);
        dp[0] = 0;

        for (int i = 1; i <= m; i++)
        {
            for (int j = coins[i - 1]; j <= n; j++)
            {
                dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        return dp[n] == INF ? -1 : dp[n];
    }
};
class Solution {
public:
    int numSquares(int n)
    {
        int m = sqrt(n);
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= m; i++)
        {
            for (int j = i * i; j <= n; j++)
            {
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
};
class Solution {
public:
    int getrob(vector<int>& nums, int begin, int end)
    {
        if (begin > end) return 0;
        int n = nums.size();
        vector<int> f(n), g(n);
        f[begin] = nums[begin];
        g[begin] = 0;

        for (int i = begin + 1; i <= end; i++)
        {
            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[end], g[end]);
    }
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        int x = nums[0] + getrob(nums, 2, n - 2);
        int y = getrob(nums, 1, n - 1);

        return max(x, y);
    }
};
class Solution {
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = nums[0];
        g[0] = 0;

        for (int i = 1; i < n; i++)
        {
            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[n - 1], g[n - 1]);
    }
};
class Solution {
public:
    vector<vector<int>> generate(int n)
    {
        vector<vector<int>> dp;
        for (int i = 1; i <= n; i++)
        {
            vector<int> tmp(i, 1);
            dp.push_back(tmp);
        }

        for (int i = 2; i < n; i++)
        {
            for (int j = 1; j < i; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }

        return dp;
    }
};
class Solution {
public:
    int climbStairs(int n)
    {
        vector<int> dp(n + 1, 1);
        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};